def solve(rectangles, queries):
acc = [[0] * 1001 for _ in range(1001)]
for hi, wi in rectangles:
acc[hi][wi] += hi * wi
for r in range(1001):
for c in range(1001):
acc[r][c] += acc[r-1][c] + acc[r][c-1] - acc[r-1][c-1]
ans = []
for hs, ws, hb, wb in queries:
cur = acc[hb-1][wb-1] - acc[hb-1][ws] - acc[hs][wb-1] + acc[hs][ws]
ans.append(cur)
return ans
def main():
t = int(input())
output = []
for _ in range(t):
n, q = read_ints()
rectangles = [read_ints() for _ in range(n)]
queries = [read_ints() for _ in range(q)]
ans = solve(rectangles, queries)
output += ans
print_int_lines(output)
def read_ints():
return [int(c) for c in input().split()]
def print_int_lines(lst):
print('\n'.join(map(str, lst)))
if __name__ == "__main__":
main()
#include <bits/stdc++.h>
# define int long long
using namespace std;
const int cnst = 1e3+5;
// const int mod = 1e9+7;
bool mutipletestcase = true;
void solve() {
int n, q;
cin >> n >> q;
int presum2d[cnst][cnst];
memset(presum2d, 0, sizeof(presum2d));
for(int i = 1; i<=n; i++) {
int a, b; cin >> a >> b;
presum2d[a][b] += (a*b);
}
for(int i = 1; i<=cnst-5; i++) {
for(int j = 1; j<=cnst-5; j++) {
presum2d[i][j] += presum2d[i-1][j]+presum2d[i][j-1]-presum2d[i-1][j-1];
}
}
while(q--) {
int rst, cst, rnd, cnd; cin >> rst >> cst >> rnd >> cnd;
cout << presum2d[rnd-1][cnd-1]-presum2d[rst][cnd-1]-presum2d[rnd-1][cst]+presum2d[rst][cst] << endl;
}
}
signed main() {
ios_base::sync_with_stdio(false);
int t = 1;
if(mutipletestcase) cin >> t;
while(t--) solve();
}235A - LCM Challenge | 1075B - Taxi drivers and Lyft |
1562A - The Miracle and the Sleeper | 1216A - Prefixes |
1490C - Sum of Cubes | 868A - Bark to Unlock |
873B - Balanced Substring | 1401D - Maximum Distributed Tree |
1716C - Robot in a Hallway | 1688B - Patchouli's Magical Talisman |
99A - Help Far Away Kingdom | 622B - The Time |
1688C - Manipulating History | 1169D - Good Triple |
1675B - Make It Increasing | 588A - Duff and Meat |
1541B - Pleasant Pairs | 1626B - Minor Reduction |
1680A - Minimums and Maximums | 1713A - Traveling Salesman Problem |
1713B - Optimal Reduction | 1710A - Color the Picture |
1686B - Odd Subarrays | 251A - Points on Line |
427C - Checkposts | 1159A - A pile of stones |
508A - Pasha and Pixels | 912A - Tricky Alchemy |
1249A - Yet Another Dividing into Teams | 1713C - Build Permutation |